package com.wtgroup.demo.mianshi.算法.字符串.字符串匹配;

import com.wtgroup.demo.common.util.Tools;
import org.junit.Test;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/8 16:40
 */
public class KMP {

    @Test
    public void testGetNextArray() {
        String[] inputs = {"acdbstacdtxeacdbstacdbk", "abc", "m", "xxx", "xxy", "aaaa", "aavb"};
        for (String input : inputs) {
            int[] res = getNextArray(input);
            Tools.printArray(res);
            Tools.printArray(getNextArray2(input));
        }
    }

    @Test
    public void testKmp() {
        String[][] inputs = {
                {"abcdefghi", "def"},
                {"aaaaaatbbb", "at"},
                {"ljlj", "7777777777777"},
                {"abxxxxxxabxxx", "ab"},
                {"fljslgjssfglsj", "8888"}
        };

        for (String[] input : inputs) {
            int res = kmp(input[0], input[1]);
            System.out.println(res);
        }
    }


    /**
     * kmp
     *
     * 01:23 https://ke.qq.com/webcourse/index.html#cid=3067253&term_id=103187834&taid=10646313396784501&type=1024&vid=5285890813652574166
     * @param str 大串
     * @param pattern 待匹配小串
     */
    public static int kmp(String str, String pattern) {
        if (pattern.length() == 0 || str.length() < pattern.length()) {
            return -1;
        }

        int[] nextArr = getNextArray(pattern);
        int i = 0, j = 0;
        while (i < str.length() && j < pattern.length()) {
            if (str.charAt(i) == pattern.charAt(j)) {
                i++; j++;
            } else if (nextArr[j] == -1) { // j==0
                i++; // 开启新的周期, 此时 j 必在0的位置
            } else { // 索引回退
                j = nextArr[j];
            }
        }

        return j < pattern.length() ? -1 : i - j;
    }

    /**
     * 我的逻辑, 两层循环, 回路直.
     * @param pattern NotEmpty
     */
    public static int[] getNextArray(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1;

        for (int i = 1; i < m; i++) {
            int preNext = next[i-1];
            // i 的 next 看 i-1 及其之前的最长前后缀
            char cur = pattern.charAt(i-1);

            // 继续看 next[i-1] 的 next
            while ( preNext >= 0 && cur != pattern.charAt(preNext)) {
                preNext = next[preNext];
            }
            // 特殊的, -1 + 1 = 0 也成立
            next[i] = preNext + 1;
        }

        return next;
    }

    /**
     * 一层循环(左神思路)
     *
     * 01:59 https://ke.qq.com/webcourse/index.html#cid=3067253&term_id=103187834&taid=10646313396784501&type=1024&vid=5285890813652574166
     * @param pattern NotEmpty
     * @return
     */
    public static int[] getNextArray2(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1;
        if (m==1) {
            return next;
        }
        next[1] = 0;

        int i = 2;
        int cn = 0;
        while (i < m) {
            if (pattern.charAt(cn) == pattern.charAt(i - 1)) {
                next[i++] = ++cn; // 更新next的同时, 后面如果进到这个分支里直接就可以用了
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }

        return next;
    }


}
